package algorithmic_data_structure.动态规划;

/**
 * 给一个整数，返回不重复的组合方案
 * 1 : {1}
 * 2 : {1,1},{2}
 * 3 : {1,1,1},{1,2},{3}
 * 4 : {1,1,1,1},{1,1,2},{2,2},{1,3},{4}
 */
public class 整数拆分 {
    public static int ways(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
//        return process(1, n);
//        return dp1(n);
        return dp2(n);
    }
    //拆分方法就是 每次拆出来的数都不能比上一次拆出来的要小，所以一开始pre = 1，因为拆出来的数不能小于1
    //至于拆出本身的这种方案会在 rest = 0 时得出

    /**
     * @param pre  上一次拆出来的数
     * @param rest 还剩rest要拆
     * @return 返回拆rest且 每次拆出来的数不小于pre的方案数
     */
    private static int process(int pre, int rest) {
        if (rest == 0) {//本身
            return 1;
        }
        if (pre > rest) {
            return 0;
        }
        int res = 0;
        for (int i = pre; i <= rest; i++) {
            res += process(i, rest - i);
        }
        return res;
    }

    private static int dp1(int n) {
        int[][] dp = new int[n + 1][n + 1];
        dp[1][1] = 1;
        for (int pre = 1; pre <= n; pre++) {
            dp[pre][0] = 1;     // 只拆出本身 就是 一种方案
            dp[pre][pre] = 1;   // 已经拆出pre，剩下的 rest = pre，那么 rest 只能拆分为 rest,0
        }
        for (int pre = n - 1; pre >= 1; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                int res = 0;
                for (int i = pre; i <= rest; i++) {
                    res += dp[i][rest - i];
                }
                dp[pre][rest] = res;
            }
        }
//        PrintUtil.printArray(dp);
        return dp[1][n];
    }
    private static int dp2(int n) {
        int[][] dp = new int[n + 1][n + 1];
        dp[1][1] = 1;
        for (int pre = 1; pre <= n; pre++) {
            dp[pre][0] = 1;     // 只拆出本身 就是 一种方案
            dp[pre][pre] = 1;   // 已经拆出pre，剩下的 rest = pre，那么 rest 只能拆分为 rest,0
        }
        for (int pre = n - 1; pre >= 1; pre--) {
            for (int rest = pre + 1; rest <= n; rest++) {
                dp[pre][rest] = dp[pre+1][rest];
                dp[pre][rest] += dp[pre][rest-pre];

            }
        }
//        PrintUtil.printArray(dp);
        return dp[1][n];
    }
}